package demo9;

import java.util.HashMap;

/**
 * LRU缓存 Least Recently Used 最近最久未使用算法
 * 关键点：
 *      1、一个最大容量、两个API
 *      2、保证都是O(1)的时间复杂度
 *      3、上一次访问的元素在第一个
 * 插入快、查找快、删除快
 * Map? 不是有序的
 * 双向链表 + 散列表
 * 先改存储，再改隐射关系
 * cache.put(1, 1);
 * cache.put(2, 2);
 * cache.get(1);       // 返回  1
 * cache.put(3, 3);    // 该操作会使得密钥 2 作废
 * cache.get(2);       // 返回 -1 (未找到)
 * cache.put(4, 4);    // 该操作会使得密钥 1 作废
 * cache.get(1);       // 返回 -1 (未找到)
 * cache.get(3);       // 返回  3
 * cache.get(4);       // 返回  4
 *
 */
public class LruTest {
    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(1,1);
        lru.put(2,2);
        System.out.println(lru.get(1));
        lru.put(3,3);
        System.out.println(lru.get(2));
        lru.put(4,4);
        System.out.println(lru.get(1));
        System.out.println(lru.get(3));
        System.out.println(lru.get(4));
    }
}

class LRUCache {

    int capacity;
    DoubleList list;
    HashMap<Integer,Node> map;  // node表示映射关系

    // 初始化
    public LRUCache(int capacity) {
        this.capacity = capacity;
        list = new DoubleList();
        map = new HashMap<>();
    }


    /*
    * 没有
    * 有
    * */
    public int get(int key) {
        if(!map.containsKey(key)){
            // 没有
            return -1;
        }
        // 有
        int res =  map.get(key).val;
        put(key,res);
        return res;
    }

    public void put(int key, int value) {
        Node node = new Node(key,value);
        if(map.containsKey(key)){
            list.remove(map.get(key));  // 先删掉
            list.addFirst(node);
            map.put(key,node);
        }else{
            // 不重复
            if(capacity == list.size()){
                Node last = list.removeLast();  // 删除 最后一个节点
                map.remove(last.key);
            }
            list.addFirst(node);
            map.put(key,node);
        }
    }
}


// 定义双向链表
// 存储数据
/*
* 1、正常添加
* 2、重复的key
* 3、容量满了
* */
class DoubleList{
    private Node head;
    private Node tail;
    private int size;


    DoubleList(){
        head = new Node(0,0);  // 注意：这里头尾各指向一个无用的节点
        tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }


    void addFirst(Node cur){// 头插法
        Node next = head.next;
        cur.next =  next;
        next.pre = cur;
        head.next = cur;
        cur.pre = head;
        size++;
    }

    void remove(Node cur){ // 删除node节点
        Node pre = cur.pre;
        pre.next = cur.next;
        pre.next.pre = pre;
        size--;
    }

    Node removeLast(){    // 容量满了,删除最后一个元素
        if(size == 0){
            return null;
        }
        Node del = tail.pre;
        remove(del);
        return del;
    }

    int size(){
        return size;
    }
}

// 定义节点
class Node{

    int key,val;
    Node next,pre;


    Node(int k,int v){
        this.key = k;
        this.val = v;
    }
}
